package com.sise.Stack;

import java.util.Deque;
import java.util.LinkedList;

/**
 *      155. 最小栈    (剑指 Offer 30. 包含min函数的栈)
 *
 *      设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
 *      push(x) —— 将元素 x 推入栈中。
 *      pop()—— 删除栈顶的元素。
 *      top()—— 获取栈顶元素。
 *      getMin() —— 检索栈中的最小元素。
 */
public class _offer_30_MinStack {

    Deque<Integer> xStack;              // 栈
    Deque<Integer> minStack;

    public _offer_30_MinStack() {
        xStack = new LinkedList<>();
        minStack = new LinkedList<>();
        minStack.push(Integer.MAX_VALUE);
    }

    public void push(int x) {
        xStack.push(x);

        if (minStack.peek() < x){
            minStack.push(minStack.peek());
        }else {
            minStack.push(x);
        }
    }

    public void pop() {
        xStack.pop();
        minStack.pop();
    }

    public int top() {
        return xStack.peek();
    }

    public int min() {
        return minStack.peek();
    }
}
